/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/largest-rectangle-in-histogram
   @Language: C++
   @Datetime: 19-07-08 13:06
   */

// Method 1
class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		stack<int> pos; // MaxStack
		int mx = 0;
		for (int i=0; i<=heights.size();){
			if(pos.size()<1 || (i<heights.size() && heights[pos.top()]<heights[i]))
				pos.push(i++);		// record current max number pos
			else{
				int h = heights[pos.top()];
				pos.pop();
				if (pos.size()==0) mx = max(mx, i*h);
				else mx = max(mx,(i-pos.top()-1)*h);
			}
		}
		return mx;
	}
};

// Method 2
class Solution {
public:
	int largestRectangleArea(vector<int>& heights) {
		stack<int> pos; // MaxStack
		int mx=0, i=0;
		for(heights.push_back(0); i<heights.size(); pos.push(i++)){
			while(pos.size() && heights[pos.top()]>heights[i]){
				int h=heights[pos.top()];
				pos.pop();
				mx=max(mx,pos.size()?(i-pos.top()-1)*h:i*h);
			}
		}
		return mx;
	}
};
